package _11_整理题目._4_动态规划._背包问题;

import org.junit.Test;

/**
 * dp[i][j] 的意义
 *      对于前i个物品，当前背包的容量为j时，这种情况下背包可以装下的最大价值
 *      最终要的是 dp[n][V]，所以 int[][] dp = new int[n+1][V+1]
 * 初始值
 *      dp[i][0] 表示容量为 0 时 装 i 个物品的 价值 = 0
 *      dp[0][j] 表示装 0 个物品时的 价值 = 0
 * 状态转移方程
 *      第 i 个物品放不放 产生的价值，即
 *      如果 物品的体积 > j ，不放，此时 dp[i][j] = dp[i-1][j]
 *      否则放，需要比较放不放的max，此时 dp[i][j] = math.max(aa, bb)
 *                                     不放  aa = dp[i-1][j]
 *                                      放   bb = dp[i-1][j-vw[i-1][0]] + vw[i-1][1]
 */
public class _01_01背包 {
    
    public int knapsack (int V, int n, int[][] vw) {
        int[][] dp = new int[n+1][V+1];
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=V; j++) {
                if(vw[i-1][0] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-vw[i-1][0]] + vw[i-1][1]);
                }
            }
        }
        return dp[n][V];
    }
    
    @Test
    public void main() {
        int V =10, n = 2;
        int[][] vw = {{1, 3}, {10, 4}};
        assert knapsack(V, n, vw) == 4;
    }
}
